#include <vector>
using namespace std;

void swap(vector<int> nums, int i, int j)
{
	int temp = nums[i];
	nums[i] = nums[j];
	nums[j] = temp;
}

vector<int> bubbleSort(vector<int> nums)
{
	for (int i = 0; i < nums.size() - 1; i++)
	{
		for (int j = 0; j < nums.size() - 1 - i; j++)
		{
			if (nums[j] > nums[j + 1])
				swap(nums, j, j + 1);
		}
	}
	return nums;
}

vector<int> selectSort(vector<int> nums)
{
	for (int i = 0; i < nums.size() - 1; i++)
	{
		int minIndex = nums[i];
		for (int j = i; j < nums.size(); j++)
		{
			if (nums[j] < nums[minIndex])
				minIndex = j;
		}
		swap(nums, i, minIndex);
	}
	return nums;
}

vector<int> insertSort(vector<int> nums)
{
	for (int i = 1; j < nums.size(); j++)
	{
		for (int j = i; j > 0 && nums[j] < nums[j - 1]; j--)
		{
			swap(nums, j, j - 1);
		}
	}
	return nums;
}

vector<int> shellSort(vector<int> nums)
{
	for (int gap = nums.size() / 2; gap > 0; gap /= 2)
	{
		for (int i = gap; i < nums.size(); i++)
		{
			for (int j = i; j - gap >= 0 && nums[j] < nums[j - gap]; j -= gap)
			{
				swap(nums, j, j - gap);
			}
		}
	}
	return nums;
}

vector<int> quickSort(vector<int> nums)
{
	subSort(nums, 0, nums.size() - 1);
}

void subSort(vector<int> nums, int start, int end)
{
	if (start >= end)
		return;
	int i = start, j = end;
	while (i < j)
	{
		while (i < j && nums[i] < nums[j])
			i++;
		swap(nums, i, j);
		while (i < j && nums[i] <= nums[j])
			j--;
		swap(nums, i, j);
	}
	subSort(nums, start, i - 1);
	subSort(nums, i + 1, end);
}

vector<int> mergeSort(vector<int> nums)
{
	if (nums.size() <= 1)
		return nums;
	const int mid = nums.size() / 2;
	vector<int> left, right;
	vector<int> nums1 = mergeSort(vector<int>(nums.begin(), nums.begin() + mid));
	vector<int> nums2 = mergeSort(vector<int>(nums.begin() + mid, nums.end()));
	return merge(nums1, nums2);
}

vector<int> merge(vector<int> nums1, vector<int> nums2)
{
	int i = 0, j = 0;
	vector<int> result;
	whlie(i < nums1.size() && j < nums2.size())
	{
		if (nums1[i] < nums2[j])
			result.push_back(nums1[i++]);
		else
			result.push_back(nums2[j++]);
	}
	whlie(i < nums1.size())
			result.push_back(nums1[i++]);
	whlie(j < nums2.size())
			result.push_back(nums2[j++]);
	return result;
}

vector<int> countSort(vector<int> nums)
{
	const int max = *max_element(nums, nums.begin(), nums.end());
	vector<int> buckets(max + 1, 0);
	vector<int> result;
	for (int i = 0; i < nums.size(); i++)
	{
		++buckets[nums[i]];
	}
	for (int i = 0; i < buckets.size(); i++)
	{
		while (buckets[i]--)
			result.push_back(i)
	}
	return result;
}

vector<int> bucketsSort(vector<int> nums)
{
	const int min = *min_element(nums, nums.begin(), nums.end());
	const int max = *min_element(nums, nums.begin(), nums.end());
	const int bucketNum = (max - min) / 5 + 1;
	vector<vector<int>> buckets(bucketNum);

	for (int i = 0; i < nums.size(); i++)
	{
		const int index = (i - min) / 5;
		buckets[index].push_back(nums[i]);
	}
	const vector<int> result;
	for (int i = 0; i < buckets.size(); i++)
	{
		sort(buckets[i], buckets[i].begin(), buckets[i].end());
		result.insert(result.end(), buckets[i].begin(), buckets[i].end());
	}
	return result;
}
